public class Test17 {
    public static ListNode merge(ListNode head1,ListNode head2){
        if(head1 == null) return head2;
        if(head2 == null) return head1;
        ListNode root = new ListNode();
        ListNode temp = root;
        while(head1 != null && head2 != null){
            if(head1.val < head2.val) {
                temp.next = head1;
                head1 = head1.next;

            }else{
                temp.next = head2;
                head2 = head2.next;
            }
            temp = temp.next;
        }
        if(head1 != null) temp.next = head1;
        if(head2 != null) temp.next = head2;

        return root.next;
    }

    public static ListNode merge2(ListNode head1,ListNode head2){
        if(head1 == null) return head2;
        if(head2 == null) return head1;
        if(head1.val < head2.val) {
            head1.next = merge2(head1.next,head2);
            return head1;
        }
        else {
            head2.next = merge2(head1,head2.next);
            return head2;
        }

    }


    public static void printList(ListNode head){
        ListNode temp = head;
        while (temp != null){
            System.out.print(temp.val);
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ListNode head = new ListNode();
        head.val = 1;

        head.next = new ListNode();
        head.next.val = 3;

        head.next.next = new ListNode();
        head.next.next.val = 5;

        head.next.next.next = new ListNode();
        head.next.next.next.val = 6;

        ListNode middle = head.next.next.next.next = new ListNode();
        head.next.next.next.next.val = 7;

        ListNode head2 = new ListNode();
        head2.val = 2;

        head2.next = new ListNode();
        head2.next.val = 4;

        head2.next.next = new ListNode();
        head2.next.next.val = 8;

        head2.next.next.next = new ListNode();
        head2.next.next.next.val = 9;

        ListNode middle2 = head.next.next.next.next = new ListNode();
        head.next.next.next.next.val = 10;

        //ListNode merge = merge(head, head2);
        ListNode merge2 = merge2(head,head2);
        //printList(merge);
        printList(merge2);

    }
}
